#pragma once
#include <iostream>
#include <vector>
#include <set>
#include "Rectangle.h"
#include "SocialNode.h"
#include "Constants.h"
using namespace std;

struct ComPoint {
	int val, degree;
	ComPoint(int val, int degree) : val(val), degree(degree) {}
};

struct Community {
	int label;
	vector<int> socialPoint;
	Rectangle* rect;
	std::list<std::pair<int, int>> com_topk;
	unordered_map<int, vector<int>> live_node;
	unordered_map<int, int> count_v;

	Community(int comm_label) {
		label = comm_label;
	}

	void pre_influence(vector<SocialNode*> nodes , unordered_set<int> target_user) {
		for (auto id : socialPoint) {
			int label = nodes[id]->pre_community_label;
			for (auto nei : nodes[id]->socialOutEdge) {
				if (nodes[nei.first]->pre_community_label != label) continue;
				if (target_user.find(nei.first) == target_user.end()) continue; 
				if (nei.second > 0.5) {
					nodes[id]->canInfulence.emplace(nei.first); 
					nodes[id]->binf ++; 
					nodes[nei.first]->beInfluence.emplace(id); 
				}
			}
		}
	}

	void getMBR(vector<SocialNode*> nodes) {
		rect = new Rectangle(nodes[socialPoint[0]]->x, nodes[socialPoint[0]]->y);
		for (int i = 1; i < socialPoint.size(); i++) {
			float x = nodes[socialPoint[i]]->x;
			float y = nodes[socialPoint[i]]->y;
			rect->getBoundingRect(x, y);
		}
	}

	void findTopK(vector<SocialNode*> nodes, int k, unordered_set<int> target_user) { 
		pre_influence(nodes , target_user);
		k = socialPoint.size() > k ? k : socialPoint.size();
		set<int> init_set;
		std::list<std::pair<int, int>> kmax = Iteration(nodes, k, init_set); 
		if (kmax.size() == 0) return;
		init_set.emplace(kmax.begin()->first); 
		auto beg = kmax.begin();
		pair<int, int> temp = { beg->first , beg->second };
		com_topk.emplace_back(temp);
		change_Binf(nodes, beg->first);
		kmax.pop_front(); 

		while (init_set.size() < k) {
			auto beg = kmax.begin();
			auto behind = kmax.end();
			if ((--behind) == beg) {
				init_set.emplace(beg->first);
				temp = { beg->first , nodes[beg->first]->binf };
				com_topk.emplace_back(temp);
				break;
			}
			if (nodes[beg->first]->binf < (++beg)->second) {
				kmax = Iteration(nodes, k - init_set.size() , init_set);
			}
			init_set.emplace(kmax.begin()->first);
			temp = { kmax.begin()->first , kmax.begin()->second };
			com_topk.emplace_back(temp);
			change_Binf(nodes, temp.first);
			kmax.pop_front();
		}
	}

	void change_Binf(vector<SocialNode*> nodes , int nodeId) {
		for (auto num : nodes[nodeId]->canInfulence) {
			for (auto iter : nodes[num]->beInfluence) {
				nodes[iter]->binf --;
			}
			nodes[num]->beInfluence.clear();
		}
	}

	std::list<std::pair<int, int>> findTopKPart(vector<SocialNode*> nodes, int k, unordered_set<int> target_user) { 
		pre_influence(nodes, target_user);
		std::list<std::pair<int, int>> top_k;
		k = socialPoint.size() > k ? k : socialPoint.size();
		set<int> init_set;
		std::list<std::pair<int, int>> kmax = Iteration(nodes, k, init_set);
		if (kmax.size() == 0) return com_topk;
		init_set.emplace(kmax.begin()->first); 
		auto beg = kmax.begin();
		pair<int, int> temp = { beg->first , beg->second };
		top_k.emplace_back(temp);
		change_Binf(nodes, beg->first);
		kmax.pop_front(); 

		while (init_set.size() < k) {
			auto beg = kmax.begin();
			auto behind = kmax.end();
			if ((--behind) == beg) {
				init_set.emplace(beg->first);
				temp = { beg->first , nodes[beg->first]->binf };
				top_k.emplace_back(temp);
				break;
			}
			if (nodes[beg->first]->binf < (++beg)->second) {
				kmax = Iteration(nodes, k - init_set.size() , init_set);
			}
			init_set.emplace(kmax.begin()->first);
			temp = { kmax.begin()->first , kmax.begin()->second };
			top_k.emplace_back(temp);
			change_Binf(nodes, temp.first);
			kmax.pop_front();
		}
		return top_k;
	}

	std::list<std::pair<int, int>> Iteration(vector<SocialNode*> nodes, int k, set<int>& init_set) { 
		std::list< std::pair<int, int> > kmax;
		int size = 0;
		for (auto index : socialPoint) {
			if (init_set.find(index) != init_set.end()) continue;
			if (size < k) {
				insertToList(kmax, { index , nodes[index]->binf }); 
				size ++;
				continue;
			}

			auto last = kmax.end();
			last --;
			if (last->second >= nodes[index]->binf) { 
				continue;
			}
			insertToList(kmax, { index , nodes[index]->binf }); 
			kmax.pop_back(); 
		}
		return kmax;
	}

	void insertToList(std::list<std::pair<int, int>>& kmax, pair<int, int> cur) {
		if (kmax.empty()) {
			kmax.emplace_back(cur);
			return;
		}
		auto beg = kmax.begin();
		while (beg != kmax.end()) {
			if (cur.second > beg->second) {
				kmax.emplace(beg, cur);
				break;
			}
			beg++;
		}
		if (beg == kmax.end()) {
			kmax.emplace(beg, cur);
		}
	}

	unordered_set<int> vector_to_set() {
		unordered_set<int> target_user;
		for (int i = 0; i < socialPoint.size(); i++) {
			target_user.emplace(socialPoint[i]);
		}
		return target_user;
	}

};